An ATM network is a communication intemetwork which generally includes multiple LAN switches or end-stations interconnected across an ATM "cloud" which includes a mesh of ATM trunks and ATM switches. Each ATM switch in the cloud typically includes an ATM switching fabric architecture shared by a plurality of input-output (I/O) interfaces. Data traffic, in the form of fixed-length cells, traverses the ATM network over ATM trunks in a series of "hops" between ATM switches. The ATM switch at the end of each hop typically prepares received cell traffic for the next hop by directing the traffic through the switching fabric architecture to one or more destination I/O interfaces. A conventional ATM switching architecture is illustrated in FIG. 1. Data cells are received on I/O interfaces 101-132 associated with input ports 133-164 and are switched through fabric architecture 100 to output ports 165-196 which deliver the cells to destination I/O interfaces 101-132.
A significant technical challenge facing designers of ATM switching fabric architectures is how to guarantee delivery of cell traffic from input ports to output ports while sustaining a high level of throughput. The bandwidth of a single output port of an ATM switching fabric is usually much smaller than the cumulative bandwidth of the input ports. Thus, a scheme for queueing and dequeueing cells destined for the same output port must generally be deployed within a switching fabric to avoid instantaneous congestion. The queueing and dequeueing schemes implemented in most known ATM switching fabrics have been inefficient, either taking too many clock cycles to complete or failing to guarantee resource availability during peak traffic periods. What is needed, then, is a more efficient switching fabric which is suitable for today's high-speed, high-performance digital traffic switches.